/**
 * Created by clq on 2019/2/15.
 */
public class Merger {
    public static void main(String[] args) {
        int arr[] = {9,8,7,6,5,9,8,7,6,4,3,0,2,1,0};
        sort(arr);
        for(int i : arr) {
            System.out.println(i);
        }
    }

    public static void sort(int []arr) {
        int temp[] = new int[arr.length];
        sort(arr, 0, arr.length-1, temp);
    }

    public static void sort(int arr[], int left, int right, int temp[]){
        int mid = (left + right)/2;
        if(left < right) {
            sort(arr, left, mid, temp);
            sort(arr, mid+1, right, temp);
            merge(arr, left, mid, right, temp);
        }
    }

    public static void merge(int arr[], int left, int mid, int right, int temp[]) {
        int i = left;
        int j = mid+1;
        int t = 0;
        while (i <= mid && j <= right) {
            if(arr[i] < arr [j]) {
               temp[t++] = arr[i++];
            }else {
                temp[t++] = arr[j++];
            }
        }

        while (i <= mid) {
            temp[t++] = arr[i++];
        }

        while (j <= right) {
            temp[t++] = arr[j++];
        }
        t=0;
        while (left <= right) {
            arr[left++] = temp[t++];
        }
    }

}
